package day03;

import java.math.BigInteger;
import java.util.Scanner;

/**
 * 他想知道长度为 n 和为 s
 * 而且后一项总是比前一项增加a或者减少b的整数数列可能有多少种呢？
 * Created by MGL on 2017/4/4.
 */
public class Test03 {
    private static int lowbit(int index) {
        return index & -index;
    }

    private static void add(int index, BigInteger num, BigInteger[] tree) {
        while (index < tree.length) {
            tree[index] = tree[index].add(num);
            index += lowbit(index);
        }
    }


    private static BigInteger getSum(int index, BigInteger[] tree) {
        BigInteger sum = new BigInteger("0");
        while (index != 0) {
            sum = sum.add(tree[index]);
            index -= lowbit(index);
        }
        return sum;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
//        输入为一行用空格分开的整数 n m p (0 < n, m, p < 10^18)
        BigInteger[] tree = new BigInteger[12345 + 1];
        init(tree);
        BigInteger a1 = new BigInteger("1");
        BigInteger a2 = new BigInteger("1");
        add(1, a1, tree);
        add(2, a2, tree);
        for (int i = 3; i <= 12345; i++) {
            add(i, a1.add(a2), tree);
            BigInteger q = a2;
            a2 = a1.add(a2);
            a1 = q;
        }
        for (int i = 1; i <= 1000; i++) {
            System.out.println(getSum(i, tree));
        }
        System.out.println();
    }

    private static void init(BigInteger[] tree) {
        for (int i = 1; i < tree.length; i++) {
            tree[i] = new BigInteger("0");
        }
    }

}
